There are several things I’m good at. Solving Rubik’s Cube isn’t one of them. One of my sadist friends gave me one last Christmas. I scramble it all the time and leave it on my desk at work. Then I watch in amazement as any one of several co-workers walks up to it and solves it within the amount of time it takes to ask “Mike, what’s the fastest way to do buffered file I/O?” It’s very frustrating.
This month’s challenge idea comes not only from my own inadequacy but also from Jim Lloyd (Mountain View, CA). The goal is to solve Rubik’s Cube.
The prototype of the function you write is:
int
SolveRubiksCube(cubePtr)
RubiksCube *cubePtr;
Since I am so pathetic at solving the cube, I do not have enough insight to design an effective data structure to represent it. You get to define the RubiksCube typedef anyway you like.
Each call to SolveRubiksCube should make exactly one move. A move means turning any side any direction by 90 degrees. The function returns one of 3 values on each call to it:
-1 illegal cube condition, can’t be solved
0 made a move, but not done yet
1 made the last move, it’s solved
Your routine will be called in a loop from my test bench something like this:
ScrambleCube(cubePtr);
do {
x = SolveRubiksCube(cubePtr);
} while (x == 0);
Minimizing the number of moves to solve the cube is not important. Minimizing the total time required to solve the cube is important. If your SolveRubiksCube routine needs to keep track of some kind of state info or cached solution info between calls to it then it may use static variables to do so (or, you could incorporate that info into the RubiksCube data structure).
It is not required to detect an illegal cube condition on the first call to SolveRubiksCube, just so long as it is detected eventually (i.e. don’t go into an infinite loop if someone removes a couple of squares from your cube and puts them back in such a way that it makes the cube unsolvable).
Because I will need to be able to watch your routine’s progress, you will need to write two conversion routines:
void
MikeCubeToRubiksCube(mikePtr, rubikPtr)
MikeCube *mikePtr;
RubiksCube *rubikPtr;
void
RubiksCubeToMikeCube(rubikPtr, mikePtr)
RubiksCube *rubikPtr;
MikeCube *mikePtr;
The purpose is to convert your cube from whatever data structure you come up with into something my test bench can understand. It only knows about MikeCubes:
typedef struct CubeSide {
char littleSquare[3][3];
} CubeSide;
typedef struct MikeCube {
CubeSide face[6];
} MikeCube;
A cube has 6 CubeSides. If you look at a cube straight on then the indexes are: 0 = top, 1 = left side, 2 = front, 3 = right side, 4 = bottom, 5 = back. Within each CubeSide there is a 3x3 array of littleSquares (first index is row, second index is column). Each littleSquare is a number from 0 to 5, where each number represents one of the 6 colors that make up a cube.
So, a solved cube would have all 9 of the littleSquares for each side set to the same value. A solved cube that had the rightmost vertical column rotated counterclockwise 90 degrees would look like this:
005
005
005
111220333
111220333
111220333
442
442
442
554
554
554
The top part (the 005 lines) represent the top of the cube after the rotation. The 220 pieces are what you see on the front, the 442 lines are what you see on the bottom and the 554 pieces are what’s on the back. The value of mikePtr->face[0].littleSquare[1][2] is 5. The value of mikePtr->face[0].littleSquare[1][1] is 0 (the center square of the top).
Write to me if you have questions on this. Your conversion routines are not going to be part of your times so it doesn’t matter if they’re slow. Have fun.
---
The Rules
Here’s how it works: Each month we present a different programming challenge here. First, you write some code that solves the challenge. Second, optimize your code (a lot). Then, submit your solution to MacTech Magazine. We choose a winner based on code correctness, speed, size and elegance (in that order of importance) as well as the postmark of the answer. In the event of multiple equally-desirable solutions, we’ll choose one winner at random (with honorable mention, but no prize, given to the runners up). The prize for each month’s best solution is $50 and a limited-edition “The Winner! MacTech Magazine Programming Challenge” T-shirt (not available in stores).
To help us make fair comparisons, all solutions must be in ANSI compatible C (e.g. don’t use Think’s Object extensions). Use only pure C code. We disqualify any entries with any assembly in them (except for challenges specifically stated to be in assembly). You may call any routine in the Macintosh toolbox (e.g., it doesn’t matter if you use NewPtr instead of malloc). We test entries with the FPU and 68020 flags turned off in THINK C. We time routines with the latest THINK C (with “ANSI Settings”, “Honor ‘register’ first”, and “Use Global Optimizer” turned on), so beware if you optimize for a different C compiler. Limit your code to 60 characters wide. This helps with e-mail gateways and page layout.
We publish the solution and winners for this month’s Programmers’ Challenge two months later. All submissions must be received by the 10th day of the month printed on the front of this issue.
Mark solutions “Attn: Programmers’ Challenge Solution” and send them via e-mail – Internet progchallenge@xplain.com, AppleLink MT.PROGCHAL, CompuServe 71552,174 and America Online MT PRGCHAL. Include the solution, all related files, and your contact info. If you send via snail mail, send a disk with those items on it; see “How to Contact Us” on p. 2.
MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month. Authors grant MacTech Magazine the non-exclusive right to publish entries without limitation upon submission of each entry. Authors retain copyrights for the code.
